package leetcode.code1434;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

// 人 安排 帽子 超时， 决定每一个人给什么帽子
public class Solution {

	List<List<Integer>> hats;
	int n;
	int mod = (int) 1e9 + 7;

	public int numberWays(List<List<Integer>> hats) {
		this.n = hats.size();
		this.hats = hats;
		Map<Integer, Map<Long, Integer>> dp = new HashMap<>();
		return f(0, 0, dp);
	}

	private int f(int index, long used, Map<Integer, Map<Long, Integer>> dp) {
		if (index == n) {
			return 1;
		}
		if (dp.containsKey(index) && dp.get(index).containsKey(used)) {
			return dp.get(index).get(used);
		}
		long ans = 0;
		List<Integer> hat = hats.get(index);
		for (int h : hat) {
			if (((used >> h) & 1) == 0) {
				ans += f(index + 1, used | (1l << h), dp);
				ans %= mod;
			}
		}
		dp.computeIfAbsent(index, key -> new HashMap<>()).put(used, (int) ans);
		return (int) ans;
	}
}
